﻿/*
	用一个stack来实现非递归方式的二叉树遍历。
	
对于三种遍历，我们都使用push当前节点->push左子树->pop左子树->push右子树->pop右子树的方式。但是cout时机会有所不同。
对于前序遍历来说，每次访问到一个节点就cout；
对于中序遍历来说，每次将右子节点进栈时，把当前节点cout；
对于后序遍历来说，每次pop的时候cout。
另外我们还需要一个last_pop指针来存放上一个pop出去的节点。
如果当前节点的左右节点都不是上一个pop的节点，那么我们将左子节点入栈；
如果当前节点的左节点是上一个pop的节点，但右节点不是，那么就把右子节点入栈；
否则的话，就需要让当前节点出栈。
*/


#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <algorithm>

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x, TreeNode* l=NULL, TreeNode* r=NULL) : val(x), left(l), right(r) {}
};

class Solution {
public:
	// 中序遍历 LDR
	static int inorderTraversal(TreeNode* root, std::vector<TreeNode*>&res) {
		TreeNode* curr = root;
		std::stack<TreeNode*>  mystack;
		while (curr || !mystack.empty())
		{
			while (curr)
			{
				mystack.push(curr);
				curr = curr->left;
			}

			curr = mystack.top();
			mystack.pop();
			res.push_back(curr);

			curr = curr->right;
		}
		return 0;
	}

	// 先序遍历，DLR
	static int preorderTraversal1(TreeNode* root, std::vector<TreeNode*>& res) {
		TreeNode* curr = root;
		std::stack<TreeNode*>  mystack;

		mystack.push(root);

		while (!mystack.empty())
		{
			curr = mystack.top();
			mystack.pop();

			if (curr->right) mystack.push(curr->right);
			if (curr->left) mystack.push(curr->left);

			res.push_back(curr);

		}
		return 0;
	}
	static int preorderTraversal(TreeNode* root, std::vector<TreeNode*>& res) {
		TreeNode* curr = root;
		std::stack<TreeNode*>  mystack;

		while (NULL!=curr || !mystack.empty())
		{
			while (NULL != curr)
			{
				res.push_back(curr);
				mystack.push(curr);
				curr = curr->left;
			}
			if (!mystack.empty())
			{
				curr = mystack.top();
				mystack.pop();
				curr = curr->right;
			}

		}
		return 0;
	}

	// 后序遍历，LRD
	// 后序遍历需要记录访问状态。
	//		1、修改TreeNode，增加是否已经被访问的标识；
	//		2、增加lastnode，判断是否为栈里的上一节点
	static int postorderTraversal(TreeNode* root, std::vector<TreeNode*>& res)
	{
		TreeNode* p = NULL, *last = root;
		std::stack<TreeNode*>  mystack;

		mystack.push(root);
		while (!mystack.empty())
		{
			p = mystack.top();

			if (	(p->left == NULL && p->right == NULL)	// 没有叶子节点
				||	(last == p->left || last == p->right)	// 叶子节点已经处理过了
				)
			{
				// 该节点可以被处理了
				last = p;
				res.push_back(p);
				mystack.pop();
			}
			else
			{
				if (p->right)	mystack.push(p->right);
				if (p->left)	mystack.push(p->left);
			}
		}
		return 0;
	}
};


void print_tree(const char* str, std::vector<TreeNode*>& res)
{
	printf("%s: ", str);
	for (auto i : res) {
		printf("%d ", i->val);
	}
	printf("\n");
}


int main()
{
	TreeNode* root = new TreeNode(1,
		new TreeNode(2, 
			new TreeNode(4,
				NULL,
				new TreeNode(5)),
			NULL),
		new TreeNode(3, 
			new TreeNode(6),
			new TreeNode(7,
				new TreeNode(8)))
	);

	std::vector<TreeNode*> res1;

	// 遍历二叉树
	Solution::preorderTraversal(root, res1);
	print_tree("preorderTraversal", res1);

	return 0;
}